"""
An implementation of the halfedge data structure, sometimes known as the 
*DCEL* (double connected edge list). It is capable of storing the topology of
(planar?) graphs, which makes it very useful for handling polyedra, for instance.
"""

__all__=["Halfedge","HalfedgeDS"]

from managedlist import ManagedList   

class Halfedge:
    "A Half edge."
    
    def __init__(self, vtx, opp, nxt, prv, fac):
        """Constructor. All fields are integer numbers which are supposed to 
        be used as indices or keys to other data structures which store related
        information.
         
        @param vtx: vertex field.
        @param opp: opposite halfedge field.
        @param nxt: next halfedge field.
        @param prv: previous halfedge field.
        @param fac: face field.
        
        """
        self.vtx, self.opp, self.nxt, self.prv, self.fac = vtx, opp, nxt, prv, fac
        
    def __repr__(self):
        """Return a representation string for the object."""
        return "vtx=%d, opp=%d, nxt=%d, prv=%d, fac=%d"%(
           self.vtx, self.opp, self.nxt, self.prv, self.fac)

class HalfedgeDS:
    "A half edge Data Structure."

    def __init__ (self, face=[], vertex=[]):
        """Constructor. 
        
        @param face: an array of lists of vertex indices. 
        @param vertex: an array of vertex data (usually vertex coordinates). 
        
        The input arrays are 
        not stored directly in the data structure. Nevertheless, the length of 
        the vertex array is used to allocate an auxiliary table of vertex info, 
        and thus should be big enough to store any vertex index mentioned in 
        the face array."""
        
        # Create an array that contains one incident halfedge for each face
        self.faceh = ManagedList([None]*len(face))
        # Create an array that contains one incident halfedge for each vertex
        self.vertexh = ManagedList([None]*len(vertex))
        # Create an array for all halfedges of the model
        self.halfedge = ManagedList([])
        # Create a dictionary that maps pairs of vertex indices to halfedges 
        edgedic = {}
        # Iterate over all faces
        for iface in range(len(face)):
            f = face[iface]
            # Previous vertex of the first vertex is the last vertex
            vprev = f [-1]
            # Iterate over all vertices of face
            for iv in range(len(f)):
                v = f[iv]
                # The index of this halfedge
                ihe = len(self.halfedge)
                # See if the opposite halfedge was already entered
                if (v,vprev) in edgedic:
                    opposite = edgedic[v,vprev]
                    self.halfedge[opposite].opp = ihe
                else:
                    opposite = None
                # This halfedge must not have been entered yet
                assert ((vprev,v) not in edgedic)
                # Register this halfedge in the edge dictionary
                edgedic[(vprev,v)] = ihe
                # Compute index of previous halfedge
                if iv == 0: 
                    previous = ihe + len(f)-1
                else: 
                    previous = ihe - 1
                # Compute index of next halfedge
                if iv == len(f)-1:
                    next = ihe - len(f) + 1
                else:
                    next = ihe + 1
                # Create halfedge
                he = Halfedge(v,opposite,next,previous,iface)
                # Place it in the halfedge array
                self.halfedge.append(he)
                # Place it in the vertex array
                self.vertexh [v] = ihe
                # This v will be the vprev for the next iteration
                vprev = v
            # Place last halfedge created for the face in the face array
            self.faceh [iface] = ihe 
            
        # Clean up non-manifold models by finding border edges
        self.findBorders ()
   
    def findBorders (self):
        """Performs a cleaning up procedure after loading a mesh with unpaired
        halfedges. 
        
        Chase all loops and fix them by creating a "fake" face. If a face is
        fake, then its number is included in the self.borderface set.
        
        @return: None.
        """
        
        def nextBorder(he):
            """
            Traverse a vertex circulation starting from he and find the next
            halfedge whose opposite is None.
            
            @param he: a border halfedge, i.e., a halfedge for which opp is None.
             
            @return: the index of the next border halfedge around the vertex."""
            
            while self[he.nxt].opp != None:
                he = self[self[he.nxt].opp]
            return he.nxt
            
        def borderLoop(ihe):
            """
            Finds the border loop starting with halfedge[ihe].
            
            @param ihe: the index of a border halfedge, i.e., a halfedge for 
            which opp is None. 
            
            @return: a list of border halfedge indices."""
            loop = [ihe]
            while True:
                he = self[ihe]
                assert(he.opp == None)
                ihe = nextBorder(he)
                if ihe in loop: break
                loop.append(ihe)
            assert (loop[0]==ihe)
            return loop
            
        self.borderface=set([])
        
        for ihe in range(len(self.halfedge)):
            he = self.halfedge[ihe]
            if he.opp == None:
                loop = borderLoop(ihe)
                loop.reverse()
                # Create fake face for loop
                for iloop in range(len(loop)):
                    # Where this border edge twin will be put
                    ihetwin = len(self.halfedge)
                    if iloop == 0: 
                        previous = ihetwin + len(loop)-1
                    else: 
                        previous = ihetwin - 1
                    if iloop == len(loop)-1:
                        next = ihetwin - len(loop)+1
                    else:
                        next = ihetwin + 1
                    v = self[loop[(iloop+1) % len(loop)]].vtx
                    opposite = loop[iloop]
                    self[opposite].opp = ihetwin
                    iface = len(self.faceh)
                    hetwin = Halfedge(v,opposite,next,previous,iface)
                    self.halfedge.append(hetwin)
                # Remember one border halfedge for each loop                    
                self.faceh.append(ihetwin)
                self.borderface.add (iface)
                
    def __getitem__(self, index):
        """Indexing magic method.
        @param index: the index of a halfedge.
        @return: the halfedge corresponding to index.
        """
        return self.halfedge[index]
        
    def __repr__(self):
        """
        Representation magic method. Returns a string with a dump from
        this data structure.
        """
        l = ["halfedges:"]
        for ihe in range(len(self.halfedge)):
            he = self.halfedge[ihe]
            l.append("%4d:"%ihe + str(he))
        l.append("faces:"+",".join([str(x) for x in self.faceh]))
        l.append("vertices:"+",".join([str(x) for x in self.vertexh]))
        l.append("borderfaces:"+str(self.borderface))
        return "\n".join(l)

    def index(self, he):
        """The inverse of the __index__ method, i.e., given a halfedge 
        object, returns its index.
        @param he: a halfedge.
        @return: the index of halfedge he."""
        return self.halfedge[he.nxt].prv
        
    def invertCirculations(self):
        """Inverts all face and border circulations. This is necessary for
        some mesh models which use clockwise circulations pointing out.
        """
        newvtx = {}
        for he in self.halfedge:
            if he is not None:
                newvtx [he] = self.halfedge[he.prv].vtx
        for he in self.halfedge:
            if he is not None:
                he.prv,he.nxt = he.nxt,he.prv
                he.vtx = newvtx[he]
        for ihe in range(len(self.halfedge)):
            he = self.halfedge [ihe]
            if he is not None:
                self.vertexh[he.vtx]=ihe
        
        
    def aroundFace (self, iface):
        """Generator for the circulation of halfedges of face iface. Each
        returned element is a halfedge.
        @param iface: the face index.
        """
        
        assert (self.faceh[iface] is not None)
        ihe = lastihe = self.faceh[iface]
        while True:
            he = self.halfedge[ihe]
            yield he
            ihe = he.nxt
            if ihe == lastihe: break
            
    def aroundVertex (self,ivtx):
        """Generator for the circulation of halfedges incident on vertex ivtx.
        Each returned element is a halfedge.
        @param ivtx: a vertex index."""
        assert (self.vertexh[ivtx] is not None)
        ihe = lastihe = self.vertexh[ivtx]
        while True:
            he = self.halfedge[ihe]
            yield he
            ihe = self.halfedge[he.opp].prv
            assert (self.halfedge[ihe].vtx == ivtx)
            if ihe == lastihe: break
            
    def allFaces (self):
        """Generates one halfedge incident on each face of the model."""
        for i in self.faceh.usedindices(): 
            if i not in self.borderface: yield self.halfedge[self.faceh[i]]

    def allVertices (self):
        """Generates one halfedge incident on each vertex of the model."""
        for ihe in self.vertexh.usedvalues(): yield self.halfedge[ihe]

    def allEdges (self):
        """Generates one halfedge incident on each edge of the model."""
        for he in self.halfedge.usedvalues():
            if he.vtx < self.halfedge[he.opp].vtx: yield he 
            
    def splitEdge(self, he):
        """Splits the edge referred to by halfedge he. Creates a new
        vertex and a new edge (two halfedges). 
        @param he: one of the halfedges for the edge to be split.
        @return: a halfedge that points to the new vertex and whose nxt field
        points to the input halfedge."""
        
        ihe1 = self.halfedge.insert (None)
        ihe2 = self.halfedge.insert (None)
        ivtx = self.vertexh.insert (ihe1)
        ihe = self.index(he)
        op = self.halfedge[he.opp]
        self.halfedge[ihe1] = Halfedge (vtx=ivtx,opp=he.opp,nxt=ihe,prv=he.prv,fac=he.fac)
        self.halfedge[ihe2] = Halfedge (vtx=ivtx,opp=ihe,nxt=he.opp,prv=op.prv,fac=op.fac)
        self.halfedge[he.prv].nxt = ihe1
        he.prv = ihe1 
        self.halfedge[op.prv].nxt = ihe2
        op.prv = ihe2
        return self.halfedge[ihe1]
        
    def removeEdge(self,he):
        """Removes the edge referred to by halfedge he and vertex he.vtx. The vertex
        circulations of he.vtx and halfedge[he.prv].vtx are merged. 
        @param he: one of the halfedges of the edge to be removed.
        @return: the previous value of he.nxt (before the removal)."""
        
        ihe = self.index(he)
        op = self.halfedge[he.opp]
        for h in list(self.aroundVertex(he.vtx)):
            # Notice that we must first gather all halfedges with list() before
            # altering the vtx field, otherwise the generator will break
            h.vtx = op.vtx
        self.halfedge[he.prv].nxt = he.nxt
        self.halfedge[he.nxt].prv = he.prv
        self.halfedge[op.prv].nxt = op.nxt
        self.halfedge[op.nxt].prv = op.prv
        del self.halfedge[ihe]
        del self.halfedge[he.opp]
        return he.nxt
        
                
if __name__=="__main__":
    # A simple test for class HalfedgeDS
    hds = HalfedgeDS ([
                [3, 2, 1, 0], [7, 6, 2, 3], [4, 5, 6, 7],
                [0, 1, 5, 4], [1, 2, 6, 5], [3, 0, 4, 7] 
                ],
                [
                [-1, -1,1],[-1, -1,-1], [-1,1,-1], [-1,1,1], 
                [1, -1,1],[1, -1,-1], [1, 1,-1], [1,1,1]])
    print "Incident on vertex 0"
    print list(hds.aroundVertex(0))
    print ""
    for h in hds.aroundVertex(0):
        print h
        
    print "All Edges"
    for h in hds.allEdges():
        print h.vtx, "-", hds[h.opp].vtx
    
    print "All Faces"
    for h in hds.allFaces():
        print "Face",h.fac,":", 
        for hh in hds.aroundFace(h.fac):
            print hh.vtx, "-", 
        print ""
        
    hesplit = hds.splitEdge(hds[0])
    print "All Faces after edge split"
    print hds
    for h in hds.allFaces():
        print "Face",h.fac,":",
        for hh in hds.aroundFace(h.fac):
            print hh.vtx, "-", 
        print ""
    
    hds.removeEdge(hesplit)
    print "All Faces after edge removal"
    print hds
    for h in hds.allFaces():
        print "Face",h.fac,":",
        for hh in hds.aroundFace(h.fac):
            print hh.vtx, "-", 
        print ""
    
    hds.invertCirculations()
    print "All Faces with inverted circulations"
    for h in hds.allFaces():
        print "Face",h.fac,":",
        for hh in hds.aroundFace(h.fac):
            print hh.vtx, "-", 
        print ""
